//1. 杨辉三角II  题目链接：https://leetcode.cn/problems/pascals-triangle-ii/description/
//空间复杂度O(rowIndex)
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        //思路：相加覆盖
        vector<int> ans;
        for (int i = 0; i <= rowIndex; ++i)
        {
            int n = ans.size();
            for (int cur = 0; cur < n - 1; ++cur)
            {
                ans[cur] = ans[cur] + ans[cur + 1];
            }
            ans.insert(ans.begin(), 1);
        }
        return ans;
    }
};

//2. 找到字符串中所有字母异位词【2023-图森未来-测试开发】 题目链接：https://leetcode.cn/problems/VabMRr/description/?envType=problem-list-v2&envId=sliding-window
//时空复杂度O(N)
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int size_s = s.size(), size_p = p.size();

        if (size_s >= size_p)
        {
            map<char, int> mp1;//记录p中每个字符个数
            for (auto& e : p) { mp1[e]++; }
            map<char, int> mp2;//记录滑动窗口内的对应字符个数

            int left = 0, right = 0;
            while (left < size_s - size_p + 1)
            {
                int flag = 1;
                while (right < size_s && right - left < size_p)
                {
                    //连续字符，长度固定，每个s中的字符只要比mp1中的对应字符多，别的字符就不够
                    if (p.find(s[right]) == string::npos || ++mp2[s[right]] > mp1[s[right]])
                    {
                        flag = 0;
                        if (p.find(s[right]) != string::npos) { ++right; }//right在无关字符处停下，等待left
                        break;
                    }
                    ++right;
                }
                if (flag) { ans.push_back(left); }//满足条件

                //left右移
                ++left;
                if (mp2.find(s[left - 1]) != mp2.end())
                {
                    if (!(--mp2[s[left - 1]])) { mp2.erase(s[left - 1]); }
                    //如果右移后s[left]的次数超过，要继续移动，特殊处理
                    while (mp2.find(s[left]) != mp2.end() && left < right && mp2[s[left]] > mp1[s[left]])
                    {
                            ++left;
                            if (!(--mp2[s[left - 1]])) { mp2.erase(s[left - 1]); }
                    }
                }

                if (right < left) { right = left; }//一起越过无关字符
            }
        }
        return ans;
    }
};
